/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/edit-distance
@Language: C++
@Datetime: 16-02-09 05:48
*/

class Solution {
public:    
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    int minDistance(string A, string B) {
        // write your code here
        int la = A.length();
    	int lb = B.length();
    	int i,j;
    	vector<vector<int> > DP;
    	vector<int> dp;
    	for(j=0;j<=lb;++j)
    		dp.push_back(0);
    	for(i=0;i<=la;++i)
    		DP.push_back(dp);
    	for(i=0;i<=la;++i)
    	    DP[i][0]=i;
    	for(j=0;j<=lb;++j)
    	    DP[0][j]=j;
    	    
    	for(i=1;i<=la;++i){
    		for(j=1;j<=lb;++j){
    			int replace = DP[i-1][j-1]+(A[i-1]==B[j-1] ? 0:1);
    			int insertion = DP[i][j-1]+1;
    			int deletion = DP[i-1][j]+1;
    			replace = (replace < insertion ? replace:insertion);
    			replace = (replace < deletion ? replace:deletion);
    			DP[i][j] = replace;
    		}
    	}
    	return DP[la][lb];
    }
};
